/*
find the number of occurrence of given sum in array
EX: input : 10 5 3 2 sum=15
output: 2
it means 15=10+5
15=10+3+2
*/

#include<iostream.h>  // took 50 mins , got stuck in the wrong logic
#include<conio.h>
int arr[] = {10,5,3,2,7,8};
int givenSum = 15;
int findSumCount(int index, int currSum, int matchCount, int len)
{
             if(index == len)
                 return matchCount;
             if((currSum + arr[index]) > givenSum)
                  return    findSumCount(index+1, currSum, matchCount, len);
             else if((currSum + arr[index]) == givenSum)
             {
                  return (matchCount + 1);
             }
                  
             else
             {
                 int total = 0;
                 for(int j=index+1; j<len; j++)
                     total = total + findSumCount(j, (currSum+arr[index]), 0, len);
                 return (matchCount + total);
             }
}
int main()
{
    int matchCount = 0,currSum = 0;
    int len = sizeof(arr)/ sizeof(int);
    for(int i=0; i<len;i++)
    {
            currSum = 0;
            matchCount = matchCount + findSumCount(i, currSum, 0, len);
    }
    cout<<"\n total match count = "<<matchCount;
    getch();
    return 0;
}
